The present invention relates generally to hardware-based, fixed-point filter-banks, and more specifically to fully parallel Fast Fourier Transform (FTT) structures with constant phase (or twiddle) factors that can be optimized in hardware.
Filter-banks, such as Fast Fourier Transforms (FFTs), typically use normalized complex rotation operators called phase factors. Usually the phase factors are quantized using a fixed length quantizer without regard to their angle accuracy. The fixed length is chosen to be arbitrarily large, which can lead to wasteful hardware usage for phase factors with little benefit to filter-bank performance.
Additionally, such phase factor quantizers typically use a round-to-zero approach without considering the benefits of a round-to-nearest approach.
Fast Fourier Transforms are algorithms for computing Discrete Fourier Transforms (DFTs) faster and more efficiently. They are particularly valuable for implementing in computer hardware. FFTs are particularly well suited for use in massively parallel hardware, such as Field Programmable Gate Arrays (FPGAs) and Application-Specific Integrated Circuits (ASICs).
An FFT structure consists of simple addition, subtraction, and complex rotation operators with phase factors as given by:
                                          F            k                    =                                                    ∑                                  n                  =                  0                                                                      N                    /                    2                                    -                  1                                            ⁢                                                ⅇ                                                            -                      j                                        ⁢                                                                                  ⁢                    2                    ⁢                                                                                  ⁢                    π                    ⁢                                                                                  ⁢                                          nk                      /                                              (                                                  N                          /                          2                                                )                                                                                            ⁢                                  f                                      2                    ⁢                                                                                  ⁢                    n                                                                        +                                          W                k                            ⁢                                                ∑                                      n                    =                    0                                                                              N                      /                      2                                        -                    1                                                  ⁢                                                      ⅇ                                                                  -                        j                                            ⁢                                                                                          ⁢                      2                      ⁢                                                                                          ⁢                      π                      ⁢                                                                                          ⁢                                              nk                        /                                                  (                                                      N                            /                            2                                                    )                                                                                                      ⁢                                      f                                                                  2                        ⁢                                                                                                  ⁢                        n                                            +                      1                                                                                                          ,                            (        1        )            
where Wk are commonly referred to as phase or twiddle factors.
Traditionally, FFT structures have been constructed by re-using Digital Signal Processing (DSP) blocks and storing phase factors in ROM tables. However, with FPGAs and ASICs, it is possible to construct a fully parallel FFT structure where every algorithm component is fully implemented in concrete hardware.
This fully mapped structure means that phase factors are now constants and a good opportunity for hardware optimization. Because phase factors are constants, the complex rotation operator becomes a set of constant multipliers that can be implemented using a series of shifted adders. The number of required adders is dictated by the bit-length of the phase factors and the number of one bits that represent them. If the fixed-point length of the phase factors can be varied per factor k, while still maintaining adequate accuracy, then fewer adders will be required to implement an FFT.
Conventional approaches for determining the number of bits needed for phase factors are based on trial and error methods requiring thousands of time consuming simulation runs.
There is, therefore, a need for a variable length phase factor quantizer.